package com.chj.chuji.tijie13;

import java.util.Stack;

//https://blog.csdn.net/weixin_44178736/category_9309163.html
//https://blog.csdn.net/qq_44833724/article/details/107906921
//https://blog.csdn.net/weixin_44178736/article/details/101206810
//https://www.cnblogs.com/ehanla/p/10003420.html
//https://blog.csdn.net/weixin_44178736/article/details/101206810
//https://blog.csdn.net/weixin_44178736/article/details/101206810
//https://blog.csdn.net/xiang_6/article/details/83655162
//http://www.dtmao.cc/news_show_95533.shtml
public class BetweenSections {

	public final static int inf = (int) 1e9;
	public final static int maxm = (int) (1e5 + 5);
	public static int[] a = new int[7];
	public static int[] l = new int[7];
	public static int[] r = new int[7];
//	stack<int>stk;
	public static Stack<Integer> stk = new Stack<Integer>();
	public static int ans = 0;
	public static int n = 5;

	public static void getma() {// 求a[i]为最大值的拓展范围
//		a[0] = a[n + 1] = inf;// 保证全部元素出栈
//		while (!stk.empty())
//			stk.pop();
//		for (int i = 1; i <= n + 1; i++) {// 右
//			while (!stk.empty() && a[stk.peek()] < a[i]) {
//				r[stk.peek()] = i - 1;
//				stk.pop();
//			}
//			stk.push(i);
//		}
//		while (!stk.empty())
//			stk.pop();
//		for (int i = n; i >= 0; i--) {// 左
//			while (!stk.empty() && a[stk.peek()] <= a[i]) {
//				l[stk.peek()] = i + 1;
//				stk.pop();
//			}
//			stk.push(i);
//		}

		while (!stk.empty())
			stk.pop();

		for (int i = n; i >= 1; i--) {
			while (!stk.empty() && a[i] > a[stk.peek()])
				stk.pop();
			r[i] = stk.size() == 0 ? n : stk.peek() - 1;
			stk.push(i);
		}

		while (!stk.empty())
			stk.pop();
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && a[i] >= a[stk.peek()]) {
				stk.pop();
			}
			l[i] = stk.size() == 0 ? 1 : stk.peek() + 1;
			stk.push(i);
		}
		while (!stk.empty()) {
			stk.pop();
		}

		for (int i = 1; i <= n; i++) {
			int temp = (r[i] - i + 1 - 1) + (i - l[i] + 1 - 1) + (r[i] - i + 1 - 1) * (i - l[i] + 1 - 1);
			ans += temp * a[i];
		}
	}

//	l [0, 1, 1, 3, 4, 1, 0]
//	r [0, 1, 4, 4, 4, 5, 0]
//	a  [1000000000, 1, 8, 4, 3, 9, 1000000000]
//
//
//	l [0, 1, 2, 2, 2, 5, 0]
//	r [0, 5, 2, 3, 5, 5, 0]
//	a  [1000000000, 1, 8, 4, 3, 9, 1000000000]  

//	l [0, 1, 1, 3, 4, 1, 0]
//	r [0, 1, 4, 4, 4, 5, 0]
//	a [0, 1, 8, 4, 3, 9, 0]
//
//	l [0, 1, 2, 2, 2, 5, 0]
//	r [0, 5, 2, 3, 5, 5, 0]
//	a [0, 1, 8, 4, 3, 9, 0]

	public static void getmi() {// 求a[i]为最小值的拓展范围
//		a[0] = a[n + 1] = -1;// 保证全部元素出栈
//		while (!stk.empty())
//			stk.pop();
//		for (int i = 1; i <= n + 1; i++) {// 右
//			while (!stk.empty() && a[stk.peek()] > a[i]) {
//				r[stk.peek()] = i - 1;
//				stk.pop();
//			}
//			stk.push(i);
//		}
//		while (!stk.empty())
//			stk.pop();
//		for (int i = n; i >= 0; i--) {// 左
//			while (!stk.empty() && a[stk.peek()] >= a[i]) {
//				l[stk.peek()] = i + 1;
//				stk.pop();
//			}
//			stk.push(i);
//		}

		while (!stk.empty())
			stk.pop();

		for (int i = n; i >= 1; i--) {
			while (!stk.empty() && a[i] < a[stk.peek()])
				stk.pop();
			r[i] = stk.size() == 0 ? n : stk.peek() - 1;
			stk.push(i);
		}

		while (!stk.empty())
			stk.pop();
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && a[i] <= a[stk.peek()]) {
				stk.pop();
			}
			l[i] = stk.size() == 0 ? 1 : stk.peek() + 1;
			stk.push(i);
		}
		while (!stk.empty()) {
			stk.pop();
		}

		for (int i = 1; i <= n; i++) {
			int temp = (r[i] - i + 1 - 1) + (i - l[i] + 1 - 1) + (r[i] - i + 1 - 1) * (i - l[i] + 1 - 1);
			ans -= temp * a[i];
		}
	}

	public static void main(String[] args) {
//      cin>>n;
//      for(int i=1;i<=n;i++){
//          cin>>a[i];
//      }
//      ans=0;
//      getma();
//      getmi();

		int[] ard = new int[] { 1, 8, 4, 3, 9 };
		for (int i = 1; i <= n; i++) {
			a[i] = ard[i - 1];
		}
		getma();
		getmi();
		System.out.println(ans);
	}
}

//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<cmath>
//#include<algorithm>
//#include<stack>
//using namespace std;
//#define int long long
//const int inf=1e9;
//const int maxm=1e5+5;
//int a[maxm];
//int l[maxm],r[maxm];
//stack<int>stk;
//int ans;
//int n;
//void getma(){//求a[i]为最大值的拓展范围
//    a[0]=a[n+1]=inf;//保证全部元素出栈
//    while(!stk.empty())stk.pop();
//    for(int i=1;i<=n+1;i++){//右
//        while(!stk.empty()&&a[stk.top()]<a[i]){
//            r[stk.top()]=i-1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    while(!stk.empty())stk.pop();
//    for(int i=n;i>=0;i--){//左
//        while(!stk.empty()&&a[stk.top()]<=a[i]){
//            l[stk.top()]=i+1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    for(int i=1;i<=n;i++){
//        int temp=(r[i]-i+1-1)+(i-l[i]+1-1)+(r[i]-i+1-1)*(i-l[i]+1-1);
//        ans+=temp*a[i];
//    }
//}
//void getmi(){//求a[i]为最小值的拓展范围
//    a[0]=a[n+1]=-1;//保证全部元素出栈
//    while(!stk.empty())stk.pop();
//    for(int i=1;i<=n+1;i++){//右
//        while(!stk.empty()&&a[stk.top()]>a[i]){
//            r[stk.top()]=i-1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    while(!stk.empty())stk.pop();
//    for(int i=n;i>=0;i--){//左
//        while(!stk.empty()&&a[stk.top()]>=a[i]){
//            l[stk.top()]=i+1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    for(int i=1;i<=n;i++){
//        int temp=(r[i]-i+1-1)+(i-l[i]+1-1)+(r[i]-i+1-1)*(i-l[i]+1-1);
//        ans-=temp*a[i];
//    }
//}
//signed main(){
//    int T;
//    cin>>T;
//    while(T--){
//        cin>>n;
//        for(int i=1;i<=n;i++){
//            cin>>a[i];
//        }
//        ans=0;
//        getma();
//        getmi();
//        cout<<ans<<endl;
//    }
//    return 0;
//}
////https://ac.nowcoder.com/acm/problem/20806

//	public static void main(String[] args) {
////		int N = (int) (1e5 + 10);
//		Stack<Integer> st = new Stack<Integer>();
//		int[] l = new int[6];
//		int[] r = new int[6];
//		int[] a = new int[6];
//
//		int n = 5;
//		int sum = 0;
//		int[] ard = new int[] { 1, 8, 4, 3, 9 };
//		for (int i = 1; i <= n; i++) {
//			a[i] = ard[i - 1];
//		}
//
//		for (int i = 1; i <= n; i++) {
//			while (st.size() > 0 && a[i] <= a[st.peek()]) {
//				st.pop();
//			}
//			l[i] = st.size() == 0 ? 1 : st.peek() + 1;
//			st.push(i);
//		}
//
//		while (st.size() > 0)
//			st.pop();
//		for (int i = n; i >= 1; i--) {
//			while (st.size() > 0 && a[i] < a[st.peek()])
//				st.pop();
//			r[i] = st.size() == 0 ? n : st.peek() - 1;
//			st.push(i);
//		}
//		while (st.size() > 0) {
//			st.pop();
//		}
//
////		l [0, 1, 2, 2, 2, 5]
////		r [0, 5, 2, 3, 5, 5]
////		a [0, 1, 8, 4, 3, 9]
//		for (int i = 1; i <= n; i++) {
////			sum-=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
//			int temp = (r[i] - (i + 1) + 1) + ((i - 1) - l[i] + 1) + (r[i] - (i + 1) + 1) * ((i - 1) - l[i] + 1);
//			sum -= temp * a[i];
//		}
//		for (int i = 1; i <= n; i++) {
//			while (st.size() > 0 && a[i] >= a[st.peek()])
//				st.pop();
//			l[i] = st.size() == 0 ? 1 : st.peek() + 1;
//			st.push(i);
//		}
//		while (st.size() > 0)
//			st.pop();
//		for (int i = n; i >= 1; i--) {
//			while (st.size() > 0 && a[i] > a[st.peek()])
//				st.pop();
//			r[i] = st.size() == 0 ? n : st.peek() - 1;
//			st.push(i);
//		}
//		while (st.size() > 0)
//			st.pop();
//		for (int i = 1; i <= n; i++) {
////			sum+=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
//			int temp = (r[i] - (i + 1) + 1) + ((i - 1) - l[i] + 1) + (r[i] - (i + 1) + 1) * ((i - 1) - l[i] + 1);
//			sum += temp * a[i];
//		}
//
//		System.out.println(sum);
//	}
//
//}

//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<cmath>
//#include<algorithm>
//#include<stack>
//using namespace std;
//#define int long long
//const int inf=1e9;
//const int maxm=1e5+5;
//int a[maxm];
//int l[maxm],r[maxm];
//stack<int>stk;
//int ans;
//int n;
//void getma(){//求a[i]为最大值的拓展范围
//    a[0]=a[n+1]=inf;//保证全部元素出栈
//    while(!stk.empty())stk.pop();
//    for(int i=1;i<=n+1;i++){//右
//        while(!stk.empty()&&a[stk.top()]<a[i]){
//            r[stk.top()]=i-1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    while(!stk.empty())stk.pop();
//    for(int i=n;i>=0;i--){//左
//        while(!stk.empty()&&a[stk.top()]<=a[i]){
//            l[stk.top()]=i+1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    for(int i=1;i<=n;i++){
//        int temp=(r[i]-i+1-1)+(i-l[i]+1-1)+(r[i]-i+1-1)*(i-l[i]+1-1);
//        ans+=temp*a[i];
//    }
//}
//void getmi(){//求a[i]为最小值的拓展范围
//    a[0]=a[n+1]=-1;//保证全部元素出栈
//    while(!stk.empty())stk.pop();
//    for(int i=1;i<=n+1;i++){//右
//        while(!stk.empty()&&a[stk.top()]>a[i]){
//            r[stk.top()]=i-1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    while(!stk.empty())stk.pop();
//    for(int i=n;i>=0;i--){//左
//        while(!stk.empty()&&a[stk.top()]>=a[i]){
//            l[stk.top()]=i+1;
//            stk.pop();
//        }
//        stk.push(i);
//    }
//    for(int i=1;i<=n;i++){
//        int temp=(r[i]-i+1-1)+(i-l[i]+1-1)+(r[i]-i+1-1)*(i-l[i]+1-1);
//        ans-=temp*a[i];
//    }
//}
//signed main(){
//    int T;
//    cin>>T;
//    while(T--){
//        cin>>n;
//        for(int i=1;i<=n;i++){
//            cin>>a[i];
//        }
//        ans=0;
//        getma();
//        getmi();
//        cout<<ans<<endl;
//    }
//    return 0;
//}

//#include <stack>
//#include <cstdio>
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//const int N=1e5+10;
//typedef long long ll;
//stack <int> st;
//ll l[N],r[N],a[N];
//
//int main(){
//    int t;
//    scanf("%d",&t);
//
//    while(t--){
//        int n;
//        ll sum=0;
//        scanf("%d",&n);
//        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
//        for(int i=1;i<=n;i++){
//            while(st.size()&&a[i]<=a[st.top()]) st.pop();
//            l[i]=st.size()==0?1:st.top()+1;
//            st.push(i);
//        }
//        while(st.size()) st.pop();
//        for(int i=n;i>=1;i--){
//            while(st.size()&&a[i]<a[st.top()]) st.pop();
//            r[i]=st.size()==0?n:st.top()-1;
//            st.push(i);
//        }
//        while(st.size()) st.pop();
//        for(int i=1;i<=n;i++) sum-=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
//        for(int i=1;i<=n;i++){
//            while(st.size()&&a[i]>=a[st.top()]) st.pop();
//            l[i]=st.size()==0?1:st.top()+1;
//            st.push(i);
//        }
//        while(st.size()) st.pop();
//        for(int i=n;i>=1;i--){
//            while(st.size()&&a[i]>a[st.top()]) st.pop();
//            r[i]=st.size()==0?n:st.top()-1;
//            st.push(i);
//        }
//        while(st.size()) st.pop();
//        for(int i=1;i<=n;i++) sum+=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
//        printf("%lld\n",sum);
//    }
//
//    return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//const int maxn = 1e6 + 10;
//ll a[maxn], l[maxn], r[maxn], ans, n, t;
//ll solve()
//{
//    for (int i = 1; i <= n; ++i)
//    {
//        int j = i;
//        while (j > 1 && a[j - 1] <= a[i])//维护左区间
//            j = l[j - 1];
//        l[i] = j;
//    }
//    for (int i = n; i >= 1; --i)
//    {
//        int j = i;
//        while (j < n && a[j + 1] < a[i])//维护右区间
//            j = r[j + 1];
//        r[i] = j;
//    }
//    ll ans = 0;
//    for (int i = 1; i <= n; ++i)
//    {
//        ans += a[i] * (r[i] - l[i]);
//        ans += a[i] * (i - l[i]) * (r[i] - i);
//    }
//    return ans;
//}
//int main()
//{
//    scanf("%lld", &t);
//    while (t--)
//    {
//        scanf("%lld", &n);
//        for (int i = 1; i <= n; ++i)
//            scanf("%lld", &a[i]);
//        ans = solve();
//        for (int i = 1; i <= n; ++i)//细节操作，太强了
//            a[i] = -a[i];
//        printf("%lld\n", ans + solve());
//    }
//    return 0;
//}